package com.kobeliu.entity;

/**
 * 01背包问题
 *
 *       重量      价值
 * 物品0   1        15
 * 物品1   5        20
 * 物品2   4        30
 */
public class Demo_7 {

    public static void main(String[] args) {

        int[] weight = new int[3];  //三种物品有三种重量
        int[] value = new int[3];   //三种物品有三种价值

        int[][] dp = new int[9][3]; //9行3列  行是容量，列是物品

        //初始化数组
        weight[0] = 1;
        weight[1] = 5;
        weight[2] = 4;
        value[0] = 15;
        value[1] = 20;
        value[2] = 30;

        for (int i = 0; i < 9; i++) {
            //背包容量
            for (int j = 0; j < 3; j++) {
                //物品允许个数
                //逻辑方程
                //如果允许放入 dp[i][j] = value[j] + dp[i-weight[j]][j-1]
                //如果不允许放入 dp[i][j] = value[i][j-1]
                if(i==0) {
                    dp[i][j] = 0;
                }else if(j==0){
                    if(i-weight[0] >=0){
                        dp[i][j] = 15;
                    }
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],i-weight[j] < 0?0:value[j]+dp[i-weight[j]][j-1]);
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                if(j == 2){
                    System.out.println(" "+dp[i][j]);
                }
                else if(j==0){
                    System.out.print(dp[i][j] + " ");
                }
                else{
                    System.out.print(" " +dp[i][j]);
                }
            }
        }
    }
}
